#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    //@ysh's method, pass 34/39, Exceeding the time limit.
    // int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    // {
    //     int n = gas.size();
    //     vector<int> diff(n, 0);
    //     for (int i = 0; i < n; i++)
    //     {
    //         diff[i] = gas[i] - cost[i];
    //     }
    //     for (int i = 0; i < n; i++)
    //     {
    //         if (diff[i] < 0)
    //         {
    //             continue;
    //         }
    //         int start_index = i;
    //         int total_num = 0;
    //         int total_gas = 0;
    //         while (total_gas >= 0)
    //         {
    //             if (total_num == n)
    //             {
    //                 return i;
    //             }
    //             if (start_index == n)
    //             {
    //                 start_index = 0;
    //             }
    //             total_gas += diff[start_index];
    //             start_index++;
    //             total_num++;
    //         }
    //     }
    //     return -1;
    // }

    // book's method, violent algorithm.
    // int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    // {
    //     int n = gas.size();
    //     for (int i = 0; i < n; i++)
    //     {
    //         int surplus = gas[i] - cost[i];
    //         int index = (i + 1) % n;
    //         while (surplus > 0 && index != i)
    //         {
    //             surplus += gas[index] - cost[index];
    //             index = (index + 1) % n;
    //         }
    //         if (surplus >= 0 && index == i)
    //         {
    //             return i;
    //         }
    //     }
    //     return -1;
    // }

    // int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    // {
    //     int n = gas.size();
    //     int cur_sum = 0;
    //     int min = INT_MAX;
    //     for (int i = 0; i < n; i++)
    //     {
    //         cur_sum += gas[i] - cost[i];
    //         if (cur_sum < min)
    //         {
    //             min = cur_sum;
    //         }
    //     }
    //     if (cur_sum < 0)
    //     {
    //         return -1;
    //     }
    //     if (min >= 0)
    //     {
    //         return 0;
    //     }
    //     for (int i = n - 1; i >= 0; i--)
    //     {
    //         min += gas[i] - cost[i];
    //         if (min >= 0)
    //         {
    //             return i;
    //         }
    //     }
    //     return -1;
    // }

    int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
        int cur_sum = 0;
        int total_sum = 0;
        int start_index = 0;
        int n = gas.size();
        for (int i = 0; i < n; i++)
        {
            int diff = gas[i] - cost[i];
            total_sum += diff;
            cur_sum += diff;
            if (cur_sum < 0)
            {
                start_index = i + 1;
                cur_sum = 0;
            }
        }
        if (total_sum < 0)
        {
            return -1;
        }
        return start_index;
    }
};

int main()
{
    vector<int> gas{1, 2, 3, 4, 5};
    vector<int> cost{3, 4, 5, 1, 2};
    Solution sol;
    cout << sol.canCompleteCircuit(gas, cost) << endl;
    return 0;
}